package zhoujian.oj.leetcode;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/*
 * Given an array of integers, find two numbers such 
 * that they add up to a specific target number.
 * 
 * The function twoSum should return indices of the two numbers 
 * such that they add up to the target, where index1 must be less than index2. 
 * Please note that your returned answers (both index1 and index2) are not zero-based.
 * 
 * You may assume that each input would have exactly one solution.
 * 
 * Input: numbers={2, 7, 11, 15}, target=9
 * Output: index1=1, index2=2
*/
public class TwoSum {
	
	public int[] hashSolution(int[] numbers, int target) {
		int[] res = new int[2];
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < numbers.length; ++i) {
			map.put(numbers[i], i);
		}
		
		for (int i = 0; i < numbers.length; ++i) {
			if (numbers[i] * 2 != target && map.containsKey(target - numbers[i])) {
				res[0] = i + 1;
				res[1] = map.get(target - numbers[i]) + 1;
				return res;
			}
		}
		
		return res;
	}
	
	@Test
	public void test() {
		int[] numbers = {2, 7, 11, 15};
		int[] indices = hashSolution(numbers, 9);
		System.out.println("index1=" + indices[0] + ", index2=" + indices[1]);
	}

	public int[] twoSum(int[] numbers, int target) {
		int[] indices = new int[2];
		try {
			for (int i = 0; i < numbers.length; i++) {
				int t = target - numbers[i];
				for (int j = i + 1; j < numbers.length; j++) {
					if (t == numbers[j]) {
						indices[0] = i + 1;
						indices[1] = j + 1;
						break;
					}
				}
			}
		} catch (ArrayIndexOutOfBoundsException e) {
			System.out.println("array index out of bounds");
		}
		return indices;
    }
    	
	public static void main(String[] args) {
		int[] numbers = {2, 7, 11, 15};
		TwoSum twoSum = new TwoSum();
		int[] indices = twoSum.twoSum(numbers, 22);
		System.out.println("index1=" + indices[0] + ", index2=" + indices[1]);
	}

}
